package pers.sloera.leetcode.findMedianSortedArrays;

/**
 * 4. 寻找两个正序数组的中位数
 * <p>
 * 给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。
 * <p>
 * 请你找出这两个正序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。
 * <p>
 * 你可以假设 nums1 和 nums2 不会同时为空。
 * <p>
 * <p>
 * <p>
 * 示例 1:
 * <p>
 * nums1 = [1, 3]
 * nums2 = [2]
 * <p>
 * 则中位数是 2.0
 * 示例 2:
 * <p>
 * nums1 = [1, 2]
 * nums2 = [3, 4]
 * <p>
 * 则中位数是 (2 + 3)/2 = 2.5
 *
 * @author SloeraN
 * @version 1.0
 * @class pers.sloera.leetcode.findMedianSortedArrays.Solution
 * @date 2020/9/13
 */
public class Solution {
    // * 中位数则取中间的两位数字平均值
    //    * 偶数：比如8，中间数分别是4和5。一半是4.5。
    //           * 奇数：比如7，中间数分别是4和4。一半是3.5。
    //           * 左边：要使7和8都能得到4。`(7+1)/2`和`(8+1)/2`
    //           * 右边：要使7和8都能得到5。`7/2 + 1`和`8/2 + 1`
    //           * left: `(n+1)>>1`
    //           * right: `n>>1 + 1`
    //           * 问题的核心在于，如何快速找到第`k`位数
    // * 题目要求时间复杂度是`O(log(m+n))`，则应该联想到`二分`
    //
    //   核心逻辑：寻找两个正序数组的第k位
    //
    // * 有两个数组A，B。大小分别是m，n。
    //           * 先比较两个数组的第`k/2`个元素。`A[k/2 - 1] 与 B[k/2 - 1]`。
    //           * 比较出大小后，就可以至少去除`k/2`个元素了
    //    * `A[k/2 - 1] < B[k/2 - 1]`：至少排除`A[0] ~ A[k/2 - 1]`共`k/2`个元素。理想情况下，最多时存在`B[0] ~ B[k/2 - 2] < B[k/2 - 1]`共`k/2 - 1`个元素。总共`k - 1`个
    //  * 边界情况
    //     * `k=1`：`k/2-1 >= 0`，所以以下的比较，`k`至少为`1`。比较两个数组的左边界
    //     * 越界：为了确保使用最小值比较，此时应该选用左边界进行比较。如果是小于，应该左边界右移一位,k只能减小一位
    //     * 边界到达数组的边缘。使用另一个数组
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        return findMedianSortedArrays1(nums1, nums2);
    }

    /**
     * 使用二分
     * <p>
     * 将题目转换成寻找两个有序数组中第k(从1开始)小的数字
     *
     * @param nums1 源数组1
     * @param nums2 源数组2
     * @return double 中位数
     * @date 2020/9/13
     */
    public double findMedianSortedArrays1(int[] nums1, int[] nums2) {
        int sum = nums1.length + nums2.length;
        // int left = findK(nums1, nums2, ((sum - 1) >> 1) + 1);
        int left = findK(nums1, nums2, ((sum + 1) >> 1));
        int right = findK(nums1, nums2, (sum >> 1) + 1);
        return (left + right) / 2.0;
    }

    /**
     * 寻找nums1和nums2第k位元素（升序排序）
     *
     * <p>
     * 比较思路：<br/>
     * 要获得第k个值，两个数组比较 k/2 - 1 位置的值，则可去除0~ k/2 - 1 = k/2个数值。通过左移数组的边界去除。
     * A[k/2-1]<B[k/2-1]。则极限情况为A[0]~A[k/2-1]=k/2与B[0]~B[k/2-2]=k/2-1 共k-1个比B[k/2 -1]小的。
     * 有可能第k位在A[k/2]~A[length-1]中，去除A[0]~A[k/2-1]中肯定不包含第k小的数字。
     * </p>
     *
     * <p>
     * 边界处理：
     * <ol>
     * <li>当存在数组左边界 = 数组长度时，说明此数组已排除完，使用另一个数组</li>
     * <li>当k=1时，只需要比较两个数组的左边界，返回最小值</li>
     * <li>当数组越界时，使用左边界值，保证此值是最小，排除的时候，k减小1.</li>
     * <li>比较后：移动较小值所在数组的左边界，减小对应的k值</li>
     * </ol>
     * </p>
     *
     * @param leftNums 源数组1
     * @param rightNums 源数组2
     * @param k 位置，从1开始计算
     * @return 第k位数值（升序）
     */
    private int findK(int[] leftNums, int[] rightNums, int k) {
        // 两个数组的左边界。通过移动数组左边界来排除较小的数
        int leftLeft = 0, leftRight = 0;
        for (; ; ) {
            // 一个为空，取另一个
            if (leftLeft >= leftNums.length) {
                return rightNums[leftRight + k - 1];
            }
            if (leftRight >= rightNums.length) {
                return leftNums[leftLeft + k - 1];
            }
            // 为1时，只需返回两个数组边界中的较小值
            if (k == 1) {
                return Math.min(leftNums[leftLeft], rightNums[leftRight]);
            }
            // 数组1待查找的坐标
            int indexLeft = leftLeft + k / 2 - 1;
            int stepLeft = k / 2;
            // 越界
            if (indexLeft >= leftNums.length) {
                indexLeft = leftLeft;
                stepLeft = 1;
            }
            // 数组2待查找的坐标
            int indexRight = leftRight + k / 2 - 1;
            int stepDown = k / 2;
            // 越界
            if (indexRight >= rightNums.length) {
                indexRight = leftRight;
                stepDown = 1;
            }
            if (leftNums[indexLeft] < rightNums[indexRight]) {
                //  排除无效
                leftLeft += stepLeft;
                k -= stepLeft;
            } else {
                leftRight += stepDown;
                k -= stepDown;
            }
        }
    }
}
